package com.datastructure.test.citys;

import java.util.ArrayList;

public class Citys {

    public static void main(String[] args) {

    }

    public int citys (ArrayList<ArrayList<Integer>> m) {
        // write code here
        if(m.size()==1) return 1;
        UF uf= new UF(m.size());
        // 遍历邻接矩阵
        for(int i=0;i<m.size();i++){
            for(int j=0;j<m.get(0).size();j++){
                if(i==j) continue;
                if(m.get(i).get(j)==1){
                    // 把i和j连通
                    uf.union(i,j);
                }
            }
        }
        // 返回连通分量
        return uf.count();
    }

    static class UF{
        int count; // 连通分量
        int[] parent; // 记录父节点
        // 构造函数,n为结点个数
        UF(int n){
            this.count=n; // 初始连通分量
            this.parent=new int[n];
            for(int i=0;i<n;i++){
                parent[i]=i;  // 初始父节点指向自己
            }
        }
        // 找到x的根节点
        int find(int x){
            while(parent[x]!=x){
                x=parent[x];
            }
            return x;
        }
        // 连接p和q
        void union(int p, int q){
            int rootQ=find(q);
            int rootP=find(p);
            if(rootP!=rootQ){
                parent[rootP]=rootQ;
                count--;
            }
        }
        // 返回连通分量
        int count(){
            return count;
        }
    }
}
